1. Field of the Invention
This invention relates to a circuit device for orthogonally transforming two-dimensional discrete data such as image data, and more particularly to an orthogonal transformation device of a compact construction and operating method thereof by which discrete data arranged in a square lattice can be orthogonally transformed at a high speed.
2. Description of the Background Art
One of techniques of filter processing on two-dimensional discrete data such as image data is orthogonal transformation such as Fourier transformation or Hadamard transformation. Discrete Fourier transformation (DFT) is given by ##EQU1## where .OMEGA.1=2.pi./MxO, W1=exp (-2.pi.j/M), .OMEGA.2=2.pi./NyO, W2=exp (-2nj/N), xO is a sampling distance in the x direction in two-dimensional sampling space, and yO is a sampling distance in the y direction in two-dimensional sampling space. When such discrete Fourier transformation is represented in determinant, it is given by EQU [G]=[W1][g][W2]
In the case that the two-dimensional data array [g] is a square lattice of p.times.p (p rows and p columns), then W1=W2 and M=N in the equation above, and in this instance, the Fourier transformation matrix W becomes a symmetric matrix. Accordingly, DFT [G] can be written as EQU [G]=[W][g][W].sup.T =[W][g][W]; T: transposition.
For example, assuming M=N=3, and x0=y0=a, then, the following is obtained: ##EQU2##
Then, the following representation is obtained, ##EQU3##
Meanwhile, Hadamard transformation is given similarly by EQU Y=Hn X Hn.multidot.1/n
where Hn is a natural Hadamard matrix of degree n, and X is an n.times.n two-dimensional discrete data array.
Conventionally, FFT (fast Fourier transform) or FHT (fast Hadamard transform) is employed for such orthogonal transformation operation of a two-dimensional discrete data array.
In order to accomplish such conventional orthogonal transformation of a two-dimensional data array as described above, a multiplication of matrices must be performed twice. A multiplication of square matrices is conventionally executed in accordance with software using a computer. In performing a multiplication of square matrices in accordance with software, however, sequential steps of reading out data from a memory or a register, multiplying and adding data thus read out and storing results of the calculations into the memory or the register are required. Accordingly, there is a problem that a long period of time is required for such calculations and high speed processing cannot be attained. This also applies where such calculations are performed in accordance with a high speed transformation algorithm of FFT, FHT or the like because the number of additions and/or subtractions is required at least nlog.sub.2 n times. Accordingly, even with software processing in accordance with a conventional high speed transformation algorithm, there is a problem that a long period of time is required for multiplication of matrices and real-time processing of image data or the like cannot be achieved.
Also, where a discrete matrix arithmetic device is constructed in hardware using a scalar arithmetic units, the number of wires for interconnecting the arithmetic units increases in accordance with the number of elements of matrices, and the construction of the device is accordingly increased in scale and complicated. The degree thereof increases as an exponential function as the numbers of rows and columns of a discrete data array increase. Further, the length of wires from a data (matrix element) inputting circuit to a calculation result (multiplication result) outputting circuit is increased, which will cause a significant delay in signal transmission. Consequently, there is a problem that a multiplication of matrices cannot be achieved at a high speed.
On the other hand, a two-dimensional discrete Fourier transformation calculating device is disclosed in Japanese Patent Laying-Open Gazette No. 56-14371. The calculating device employs a technique wherein a multiplication of matrices is developed into a polynomial and individual transformation elements are calculated in accordance with the polynomial. Consequently, the construction of the device is complicated and increased in scale and a large number of calculations are required, and accordingly, prior art device cannot execute high speed calculations.
Accordingly, there has been a strong need for realization of a hardware device by which orthogonal transformation of a two-dimensional discrete data array can be executed at a high speed with hardware construction has been expected intensely in a field of image processing or the like wherein image data need be processed on the real-time basis.